SherbyNet - /page/wikibook/entry.mu

<!DOCTYPE html>

<title>Reed–Muller code</title>

</head>

Reed–Muller code

</h1>

</header>

/* start https://en.wikipedia.org/ */

.mw-parser-output .infobox-subbox{padding:0;border:none;margin:-3px;width:auto;min-width:100%;font-size:100%;clear:none;float:none;background-color:transparent}.mw-parser-output .infobox-3cols-child{margin:auto}.mw-parser-output .infobox .navbar{font-size:100%}@media screen{html.skin-theme-clientpref-night .mw-parser-output .infobox-full-data:not(.notheme)>div:not(.notheme)[style]{background:#1f1f23!important;color:#f8f9fa}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .infobox-full-data:not(.notheme)>div:not(.notheme)[style]{background:#1f1f23!important;color:#f8f9fa}}@media(min-width:640px){body.skin--responsive .mw-parser-output .infobox-table{display:table!important}body.skin--responsive .mw-parser-output .infobox-table>caption{display:table-caption!important}body.skin--responsive .mw-parser-output .infobox-table>tbody{display:table-row-group}body.skin--responsive .mw-parser-output .infobox-table th,body.skin--responsive .mw-parser-output .infobox-table td{padding-left:inherit;padding-right:inherit}}

/* end https://en.wikipedia.org/ */

</style><table class="infobox"><tbody><tr><th colspan="2" class="infobox-above">Reed-Muller code RM(r,m)</th></tr><tr><th scope="row" class="infobox-label">Named after</th><td class="infobox-data"><a href="Irving_S._Reed" title="Irving S. Reed">Irving S. Reed</a> and <a href="David_E._Muller" title="David E. Muller">David E. Muller</a></td></tr><tr><th colspan="2" class="infobox-header" style="background:#ccf;">Classification</th></tr><tr><th scope="row" class="infobox-label">Type</th><td class="infobox-data"><a href="Linear_block_code" class="mw-redirect" title="Linear block code">Linear block code</a></td></tr><tr><th scope="row" class="infobox-label"><a href="Block_code#The_block_length_n" title="Block code">Block length</a></th><td class="infobox-data"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2^{m}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 2^{m}}</annotation>

</semantics>

</math><img src="./667d0154f26e56e3f7979803f08afac16b4dcb16.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.837ex; height:2.343ex;" alt="{\displaystyle 2^{m}}" loading="lazy"></td></tr><tr><th scope="row" class="infobox-label"><a href="Block_code#The_message_length_k" title="Block code">Message length</a></th><td class="infobox-data"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k=\sum _{i=0}^{r}{\binom {m}{i}}}">

</mrow>

</mrow>

</munderover>

<mrow>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k=\sum _{i=0}^{r}{\binom {m}{i}}}</annotation>

</semantics>

</math><img src="./e3467566688b1a812e217da58a709635628ccd16.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.005ex; width:13.513ex; height:6.843ex;" alt="{\displaystyle k=\sum _{i=0}^{r}{\binom {m}{i}}}" loading="lazy"></td></tr><tr><th scope="row" class="infobox-label"><a href="Block_code#The_rate_R" title="Block code">Rate</a></th><td class="infobox-data"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k/2^{m}}">

</mrow>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k/2^{m}}</annotation>

</semantics>

</math><img src="./ab918bfe93b83cd0d22c7e74fc99dc0427fa46e3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.211ex; height:2.843ex;" alt="{\displaystyle k/2^{m}}" loading="lazy"></td></tr><tr><th scope="row" class="infobox-label"><a href="Block_code#The_distance_d" title="Block code">Distance</a></th><td class="infobox-data"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2^{m-r}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 2^{m-r}}</annotation>

</semantics>

</math><img src="./37529e5f07e85327f62413072d1f300dd5085fcc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:4.858ex; height:2.509ex;" alt="{\displaystyle 2^{m-r}}" loading="lazy"></td></tr><tr><th scope="row" class="infobox-label"><a href="Block_code#The_alphabet_Σ" title="Block code">Alphabet size</a></th><td class="infobox-data"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 2}</annotation>

</semantics>

</math><img src="./901fc910c19990d0dbaaefe4726ceb1a4e217a0f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.162ex; height:2.176ex;" alt="{\displaystyle 2}" loading="lazy"></td></tr><tr><th scope="row" class="infobox-label"><a href="Block_code#Popular_notation" title="Block code">Notation</a></th><td class="infobox-data"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle [2^{m},k,2^{m-r}]_{2}}">

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle [2^{m},k,2^{m-r}]_{2}}</annotation>

</semantics>

</math><img src="./1007673769f94fd726adff9b986f7c7939c8e39f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:13.322ex; height:3.009ex;" alt="{\displaystyle [2^{m},k,2^{m-r}]_{2}}" loading="lazy">-code</td></tr><tr><td colspan="2" class="infobox-navbar"><style data-mw-deduplicate="TemplateStyles:r1129693374">

/* start https://en.wikipedia.org/ */

.mw-parser-output .hlist dl,.mw-parser-output .hlist ol,.mw-parser-output .hlist ul{margin:0;padding:0}.mw-parser-output .hlist dd,.mw-parser-output .hlist dt,.mw-parser-output .hlist li{margin:0;display:inline}.mw-parser-output .hlist.inline,.mw-parser-output .hlist.inline dl,.mw-parser-output .hlist.inline ol,.mw-parser-output .hlist.inline ul,.mw-parser-output .hlist dl dl,.mw-parser-output .hlist dl ol,.mw-parser-output .hlist dl ul,.mw-parser-output .hlist ol dl,.mw-parser-output .hlist ol ol,.mw-parser-output .hlist ol ul,.mw-parser-output .hlist ul dl,.mw-parser-output .hlist ul ol,.mw-parser-output .hlist ul ul{display:inline}.mw-parser-output .hlist .mw-empty-li{display:none}.mw-parser-output .hlist dt::after{content:": "}.mw-parser-output .hlist dd::after,.mw-parser-output .hlist li::after{content:" · ";font-weight:bold}.mw-parser-output .hlist dd:last-child::after,.mw-parser-output .hlist dt:last-child::after,.mw-parser-output .hlist li:last-child::after{content:none}.mw-parser-output .hlist dd dd:first-child::before,.mw-parser-output .hlist dd dt:first-child::before,.mw-parser-output .hlist dd li:first-child::before,.mw-parser-output .hlist dt dd:first-child::before,.mw-parser-output .hlist dt dt:first-child::before,.mw-parser-output .hlist dt li:first-child::before,.mw-parser-output .hlist li dd:first-child::before,.mw-parser-output .hlist li dt:first-child::before,.mw-parser-output .hlist li li:first-child::before{content:" (";font-weight:normal}.mw-parser-output .hlist dd dd:last-child::after,.mw-parser-output .hlist dd dt:last-child::after,.mw-parser-output .hlist dd li:last-child::after,.mw-parser-output .hlist dt dd:last-child::after,.mw-parser-output .hlist dt dt:last-child::after,.mw-parser-output .hlist dt li:last-child::after,.mw-parser-output .hlist li dd:last-child::after,.mw-parser-output .hlist li dt:last-child::after,.mw-parser-output .hlist li li:last-child::after{content:")";font-weight:normal}.mw-parser-output .hlist ol{counter-reset:listitem}.mw-parser-output .hlist ol>li{counter-increment:listitem}.mw-parser-output .hlist ol>li::before{content:" "counter(listitem)"\a0 "}.mw-parser-output .hlist dd ol>li:first-child::before,.mw-parser-output .hlist dt ol>li:first-child::before,.mw-parser-output .hlist li ol>li:first-child::before{content:" ("counter(listitem)"\a0 "}

/* end https://en.wikipedia.org/ */

</style><style data-mw-deduplicate="TemplateStyles:r1239400231">

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbar{display:inline;font-size:88%;font-weight:normal}.mw-parser-output .navbar-collapse{float:left;text-align:left}.mw-parser-output .navbar-boxtext{word-spacing:0}.mw-parser-output .navbar ul{display:inline-block;white-space:nowrap;line-height:inherit}.mw-parser-output .navbar-brackets::before{margin-right:-0.125em;content:"[ "}.mw-parser-output .navbar-brackets::after{margin-left:-0.125em;content:" ]"}.mw-parser-output .navbar li{word-spacing:-0.125em}.mw-parser-output .navbar a>span,.mw-parser-output .navbar a>abbr{text-decoration:inherit}.mw-parser-output .navbar-mini abbr{font-variant:small-caps;border-bottom:none;text-decoration:none;cursor:inherit}.mw-parser-output .navbar-ct-full{font-size:114%;margin:0 7em}.mw-parser-output .navbar-ct-mini{font-size:114%;margin:0 4em}html.skin-theme-clientpref-night .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}@media(prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}}@media print{.mw-parser-output .navbar{display:none!important}}

/* end https://en.wikipedia.org/ */

</style></td></tr></tbody></table>

Reed–Muller codes are <a href="Error-correcting_code" class="mw-redirect" title="Error-correcting code">error-correcting codes</a> that are used in wireless communications applications, particularly in deep-space communication.<a href="#cite_note-1">[1]</a> Moreover, the proposed <a href="5G" title="5G">5G standard</a><a href="#cite_note-2">[2]</a> relies on the closely related <a href="Polar_code_(coding_theory)" title="Polar code (coding theory)">polar codes</a><a href="#cite_note-3">[3]</a> for error correction in the control channel. Due to their favorable theoretical and mathematical properties, Reed–Muller codes have also been extensively studied in <a href="Theoretical_computer_science" title="Theoretical computer science">theoretical computer science</a>.

Reed–Muller codes generalize the <a href="Reed%E2%80%93Solomon_error_correction" title="Reed–Solomon error correction">Reed–Solomon codes</a> and the <a href="Hadamard_code" title="Hadamard code">Walsh–Hadamard code</a>. Reed–Muller codes are <a href="Linear_code" title="Linear code">linear block codes</a> that are <a href="Locally_testable_code" title="Locally testable code">locally testable</a>, <a href="Locally_decodable_code" title="Locally decodable code">locally decodable</a>, and <a href="List_decoding" title="List decoding">list decodable</a>. These properties make them particularly useful in the design of <a href="Probabilistically_checkable_proof" title="Probabilistically checkable proof">probabilistically checkable proofs</a>.

Traditional Reed–Muller codes are binary codes, which means that messages and codewords are binary strings. When r and m are integers with 0 ≤ r ≤ m, the Reed–Muller code with parameters r and m is denoted as RM(r, m). When asked to encode a message consisting of k bits, where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \textstyle k=\sum _{i=0}^{r}{\binom {m}{i}}}">

</mrow>

</mrow>

</munderover>

<mrow>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \textstyle k=\sum _{i=0}^{r}{\binom {m}{i}}}</annotation>

</semantics>

</math><img src="./a4d32429d423d9654ef64cc61af4561c80f4e761.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:13.623ex; height:3.176ex;" alt="{\displaystyle \textstyle k=\sum _{i=0}^{r}{\binom {m}{i}}}" loading="lazy"> holds, the RM(r, m) code produces a codeword consisting of 2m bits.

Reed–Muller codes are named after <a href="David_E._Muller" title="David E. Muller">David E. Muller</a>, who discovered the codes in 1954,<a href="#cite_note-4">[4]</a> and <a href="Irving_S._Reed" title="Irving S. Reed">Irving S. Reed</a>, who proposed the first efficient decoding algorithm.<a href="#cite_note-5">[5]</a>

<div class="mw-heading mw-heading2"><h2 id="Description_using_low-degree_polynomials">Description using low-degree polynomials</h2></div>

Reed–Muller codes can be described in several different (but ultimately equivalent) ways. The description that is based on low-degree polynomials is quite elegant and particularly suited for their application as <a href="Locally_testable_code" title="Locally testable code">locally testable codes</a> and <a href="Locally_decodable_code" title="Locally decodable code">locally decodable codes</a>.<a href="#cite_note-6">[6]</a>

<div class="mw-heading mw-heading3"><h3 id="Encoder">Encoder</h3></div>

A <a href="Block_code" title="Block code">block code</a> can have one or more encoding functions <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\textstyle C:\{0,1\}^{k}\to \{0,1\}^{n}}">

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\textstyle C:\{0,1\}^{k}\to \{0,1\}^{n}}</annotation>

</semantics>

</math><img src="./a4ede651e90e5934254dc0c9ad8cf3312ea913d5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:20.992ex; height:3.009ex;" alt="{\textstyle C:\{0,1\}^{k}\to \{0,1\}^{n}}" loading="lazy"> that map messages <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\textstyle x\in \{0,1\}^{k}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\textstyle x\in \{0,1\}^{k}}</annotation>

</semantics>

</math><img src="./5c9577b098c111e2210387649d2f7779c5bd48a8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.943ex; height:3.009ex;" alt="{\textstyle x\in \{0,1\}^{k}}" loading="lazy"> to codewords <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\textstyle C(x)\in \{0,1\}^{n}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\textstyle C(x)\in \{0,1\}^{n}}</annotation>

</semantics>

</math><img src="./cd276b697a3e68f8253dc13898e79fa865a9a79e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:14.648ex; height:2.843ex;" alt="{\textstyle C(x)\in \{0,1\}^{n}}" loading="lazy">. The Reed–Muller code RM(r, m) has <a href="Block_code#The_message_length_k" title="Block code">message length</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \textstyle k=\sum _{i=0}^{r}{\binom {m}{i}}}">

</mrow>

</mrow>

</munderover>

<mrow>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \textstyle k=\sum _{i=0}^{r}{\binom {m}{i}}}</annotation>

</semantics>

</math><img src="./a4d32429d423d9654ef64cc61af4561c80f4e761.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:13.623ex; height:3.176ex;" alt="{\displaystyle \textstyle k=\sum _{i=0}^{r}{\binom {m}{i}}}" loading="lazy"> and <a href="Block_code#The_block_length_n" title="Block code">block length</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \textstyle n=2^{m}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \textstyle n=2^{m}}</annotation>

</semantics>

</math><img src="./80ec2f67d40d6008cabb6298c0e4d75a82f914a5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:7.331ex; height:2.176ex;" alt="{\displaystyle \textstyle n=2^{m}}" loading="lazy">. One way to define an encoding for this code is based on the evaluation of <a href="Multilinear_polynomial" title="Multilinear polynomial">multilinear polynomials</a> with m variables and <a href="Total_degree" class="mw-redirect" title="Total degree">total degree</a> at most r. Every multilinear polynomial over the <a href="Finite_field" title="Finite field">finite field</a> with two elements can be written as follows:

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<mrow>

</mrow>

<mrow>

</mrow>

</mrow>

</mrow>

</munder>

</mrow>

</munder>

<msub>

</mrow>

</msub>

</mrow>

</munder>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p_{c}(Z_{1},\dots ,Z_{m})=\sum _{\underset {|S|\leq r}{S\subseteq \{1,\dots ,m\}}}c_{S}\cdot \prod _{i\in S}Z_{i}\,.}</annotation>

</semantics>

</math>

The <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\textstyle Z_{1},\dots ,Z_{m}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\textstyle Z_{1},\dots ,Z_{m}}</annotation>

</semantics>

</math><img src="./1508b1f710b9dc393040cbcae4760226b2f855ee.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:11.082ex; height:2.509ex;" alt="{\textstyle Z_{1},\dots ,Z_{m}}" loading="lazy"> are the variables of the polynomial, and the values <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\textstyle c_{S}\in \{0,1\}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\textstyle c_{S}\in \{0,1\}}</annotation>

</semantics>

</math><img src="./55e82461188509311ecd0bef2e3c25141ff0cab9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.824ex; height:2.843ex;" alt="{\textstyle c_{S}\in \{0,1\}}" loading="lazy"> are the coefficients of the polynomial. Note that there are exactly <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\textstyle k=\sum _{i=0}^{r}{\binom {m}{i}}}">

</mrow>

</mrow>

</munderover>

<mrow>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\textstyle k=\sum _{i=0}^{r}{\binom {m}{i}}}</annotation>

</semantics>

</math><img src="./cb6d1b8e75a453a7ffa3365a6e5d3193c5170dce.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:13.623ex; height:3.176ex;" alt="{\textstyle k=\sum _{i=0}^{r}{\binom {m}{i}}}" loading="lazy"> coefficients. With this in mind, an input message consists of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\textstyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\textstyle k}</annotation>

</semantics>

</math><img src="./0d5595fc0c47452f8fc2aa6e29c3611f047714b0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\textstyle k}" loading="lazy"> values <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\textstyle x\in \{0,1\}^{k}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\textstyle x\in \{0,1\}^{k}}</annotation>

</semantics>

</math><img src="./5c9577b098c111e2210387649d2f7779c5bd48a8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.943ex; height:3.009ex;" alt="{\textstyle x\in \{0,1\}^{k}}" loading="lazy"> which are used as these coefficients. In this way, each message <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\textstyle x}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\textstyle x}</annotation>

</semantics>

</math><img src="./d951e0f3b54b6a3d73bb9a0a005749046cbce781.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\textstyle x}" loading="lazy"> gives rise to a unique polynomial <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\textstyle p_{x}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\textstyle p_{x}}</annotation>

</semantics>

</math><img src="./f8166b00c5a2a66ea1bcb0c28077e288f1cca352.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:2.431ex; height:2.009ex;" alt="{\textstyle p_{x}}" loading="lazy"> in m variables. To construct the codeword <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\textstyle C(x)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\textstyle C(x)}</annotation>

</semantics>

</math><img src="./17a1fda24a5ee512367200e191c69bfe8ec7e921.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.905ex; height:2.843ex;" alt="{\textstyle C(x)}" loading="lazy">, the encoder evaluates the polynomial <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\textstyle p_{x}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\textstyle p_{x}}</annotation>

</semantics>

</math><img src="./f8166b00c5a2a66ea1bcb0c28077e288f1cca352.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:2.431ex; height:2.009ex;" alt="{\textstyle p_{x}}" loading="lazy"> at all points <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\textstyle Z=(Z_{1},\ldots ,Z_{m})\in \{0,1\}^{m}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\textstyle Z=(Z_{1},\ldots ,Z_{m})\in \{0,1\}^{m}}</annotation>

</semantics>

</math><img src="./0d57a6922da7de5a71ba37a1577ce50228ceba7d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:27.87ex; height:2.843ex;" alt="{\textstyle Z=(Z_{1},\ldots ,Z_{m})\in \{0,1\}^{m}}" loading="lazy">, where the polynomial is taken with multiplication and addition mod 2 <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\textstyle (p_{x}(Z){\bmod {2}})\in \{0,1\}}">

<msub>

</mrow>

</msub>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\textstyle (p_{x}(Z){\bmod {2}})\in \{0,1\}}</annotation>

</semantics>

</math><img src="./b65e8aa3962197fd61a65976b7112e4d9e74bb17.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:23.009ex; height:2.843ex;" alt="{\textstyle (p_{x}(Z){\bmod {2}})\in \{0,1\}}" loading="lazy">. That is, the encoding function is defined via<math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C(x)=\left(p_{x}(Z){\bmod {2}}\right)_{Z\in \{0,1\}^{m}}\,.}">

<msub>

<mrow>

<mrow>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

<msup>

</mrow>

</msup>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle C(x)=\left(p_{x}(Z){\bmod {2}}\right)_{Z\in \{0,1\}^{m}}\,.}</annotation>

</semantics>

</math>

The fact that the codeword <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C(x)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle C(x)}</annotation>

</semantics>

</math><img src="./7f6b53682fddbe3028ffd75bd75771b86c6c7bd9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.905ex; height:2.843ex;" alt="{\displaystyle C(x)}" loading="lazy"> suffices to uniquely reconstruct <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x}</annotation>

</semantics>

</math><img src="./87f9e315fd7e2ba406057a97300593c4802b53e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}" loading="lazy"> follows from <a href="Lagrange_polynomial" title="Lagrange polynomial">Lagrange interpolation</a>, which states that the coefficients of a polynomial are uniquely determined when sufficiently many evaluation points are given. Since <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C(0)=0}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle C(0)=0}</annotation>

</semantics>

</math><img src="./38a349ca9d0c43c9d57e0ecc57a773469de6843f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.999ex; height:2.843ex;" alt="{\displaystyle C(0)=0}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C(x+y)=C(x)+C(y){\bmod {2}}}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle C(x+y)=C(x)+C(y){\bmod {2}}}</annotation>

</semantics>

</math><img src="./7df303b12c1d05862af910e8045b438a5a29ad95.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:31.32ex; height:2.843ex;" alt="{\displaystyle C(x+y)=C(x)+C(y){\bmod {2}}}" loading="lazy"> holds for all messages <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x,y\in \{0,1\}^{k}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x,y\in \{0,1\}^{k}}</annotation>

</semantics>

</math><img src="./043206429e3cc21369ae4effc8c3207ca49df9ca.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:13.132ex; height:3.176ex;" alt="{\displaystyle x,y\in \{0,1\}^{k}}" loading="lazy">, the function <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle C}</annotation>

</semantics>

</math><img src="./4fc55753007cd3c18576f7933f6f089196732029.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.766ex; height:2.176ex;" alt="{\displaystyle C}" loading="lazy"> is a <a href="Linear_map" title="Linear map">linear map</a>. Thus the Reed–Muller code is a <a href="Linear_code" title="Linear code">linear code</a>.

<div class="mw-heading mw-heading4"><h4 id="Example">Example</h4></div>

For the code RM(2, 4), the parameters are as follows:

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

<mrow>

</mrow>

</mfrac>

</mrow>

<mrow>

</mrow>

</mfrac>

</mrow>

<mrow>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

<msup>

</mrow>

</msup>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\textstyle {\begin{aligned}r&=2\\m&=4\\k&=\textstyle {\binom {4}{2}}+{\binom {4}{1}}+{\binom {4}{0}}=6+4+1=11\\n&=2^{m}=16\\\end{aligned}}}</annotation>

</semantics>

</math><img src="./08cbd8a77342331028da59791d6a7f56de3f2910.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -5.671ex; width:38.117ex; height:12.509ex;" alt="{\textstyle {\begin{aligned}r&=2\\m&=4\\k&=\textstyle {\binom {4}{2}}+{\binom {4}{1}}+{\binom {4}{0}}=6+4+1=11\\n&=2^{m}=16\\\end{aligned}}}" loading="lazy">

Let <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\textstyle C:\{0,1\}^{11}\to \{0,1\}^{16}}">

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\textstyle C:\{0,1\}^{11}\to \{0,1\}^{16}}</annotation>

</semantics>

</math><img src="./2e0313741cc34ca8a8180b9c783849bf4be99477.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:22.438ex; height:3.009ex;" alt="{\textstyle C:\{0,1\}^{11}\to \{0,1\}^{16}}" loading="lazy"> be the encoding function just defined. To encode the string x = 1 1010 010101 of length 11, the encoder first constructs the polynomial <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\textstyle p_{x}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\textstyle p_{x}}</annotation>

</semantics>

</math><img src="./f8166b00c5a2a66ea1bcb0c28077e288f1cca352.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:2.431ex; height:2.009ex;" alt="{\textstyle p_{x}}" loading="lazy"> in 4 variables:<math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\begin{aligned}p_{x}(Z_{1},Z_{2},Z_{3},Z_{4})&=1+(1\cdot Z_{1}+0\cdot Z_{2}+1\cdot Z_{3}+0\cdot Z_{4})+(0\cdot Z_{1}Z_{2}+1\cdot Z_{1}Z_{3}+0\cdot Z_{1}Z_{4}+1\cdot Z_{2}Z_{3}+0\cdot Z_{2}Z_{4}+1\cdot Z_{3}Z_{4})\\&=1+Z_{1}+Z_{3}+Z_{1}Z_{3}+Z_{2}Z_{3}+Z_{3}Z_{4}\end{aligned}}}">

<mtr>

<mtd>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}p_{x}(Z_{1},Z_{2},Z_{3},Z_{4})&=1+(1\cdot Z_{1}+0\cdot Z_{2}+1\cdot Z_{3}+0\cdot Z_{4})+(0\cdot Z_{1}Z_{2}+1\cdot Z_{1}Z_{3}+0\cdot Z_{1}Z_{4}+1\cdot Z_{2}Z_{3}+0\cdot Z_{2}Z_{4}+1\cdot Z_{3}Z_{4})\\&=1+Z_{1}+Z_{3}+Z_{1}Z_{3}+Z_{2}Z_{3}+Z_{3}Z_{4}\end{aligned}}}</annotation>

</semantics>

</math>Then it evaluates this polynomial at all 16 evaluation points (0101 means <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle Z_{1}=0,Z_{2}=1,Z_{3}=0,Z_{4}=1)}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle Z_{1}=0,Z_{2}=1,Z_{3}=0,Z_{4}=1)}</annotation>

</semantics>

</math><img src="./a4f0a184662518d184dffeb4db8dc0373ef81021.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:31.617ex; height:2.843ex;" alt="{\displaystyle Z_{1}=0,Z_{2}=1,Z_{3}=0,Z_{4}=1)}" loading="lazy">:

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p_{x}(0000)=1,\;p_{x}(0001)=1,\;p_{x}(0010)=0,\;p_{x}(0011)=1,\;}</annotation>

</semantics>

</math>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p_{x}(0100)=1,\;p_{x}(0101)=1,\;p_{x}(0110)=1,\;p_{x}(0111)=0,\;}</annotation>

</semantics>

</math>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p_{x}(1000)=0,\;p_{x}(1001)=0,\;p_{x}(1010)=0,\;p_{x}(1011)=1,\;}</annotation>

</semantics>

</math>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p_{x}(1100)=0,\;p_{x}(1101)=0,\;p_{x}(1110)=1,\;p_{x}(1111)=0\,.}</annotation>

</semantics>

</math>As a result, C(1 1010 010101) = 1101 1110 0001 0010 holds.

<div class="mw-heading mw-heading3"><h3 id="Decoder">Decoder</h3></div>

As was already mentioned, Lagrange interpolation can be used to efficiently retrieve the message from a codeword. However, a decoder needs to work even if the codeword has been corrupted in a few positions, that is, when the received word is different from any codeword. In this case, a local decoding procedure can help.

The algorithm from Reed is based on the following property:

you start from the code word, that is a sequence of evaluation points from an unknown polynomial <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\textstyle p_{x}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\textstyle p_{x}}</annotation>

</semantics>

</math><img src="./f8166b00c5a2a66ea1bcb0c28077e288f1cca352.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:2.431ex; height:2.009ex;" alt="{\textstyle p_{x}}" loading="lazy"> of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\textstyle {\mathbb {F} }_{2}[X_{1},X_{2},...,X_{m}]}">

<msub>

</mrow>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\textstyle {\mathbb {F} }_{2}[X_{1},X_{2},...,X_{m}]}</annotation>

</semantics>

</math><img src="./76e0a65256c0ab299efa809afa714be268fe96bf.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:19.528ex; height:2.843ex;" alt="{\textstyle {\mathbb {F} }_{2}[X_{1},X_{2},...,X_{m}]}" loading="lazy"> of degree at most <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\textstyle r}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\textstyle r}</annotation>

</semantics>

</math><img src="./f2dfb06630b52c9e18fcc0a4688da10774206729.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.049ex; height:1.676ex;" alt="{\textstyle r}" loading="lazy"> that you want to find. The sequence may contains any number of errors up to <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\textstyle 2^{m-r-1}-1}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\textstyle 2^{m-r-1}-1}</annotation>

</semantics>

</math><img src="./707798c9e3c12c197b03ee2deae64a9233a45afc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:10.961ex; height:2.843ex;" alt="{\textstyle 2^{m-r-1}-1}" loading="lazy"> included.

If you consider a monomial <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\textstyle \mu }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\textstyle \mu }</annotation>

</semantics>

</math><img src="./259577540a13444806174d5a1ae7662974f58085.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:1.402ex; height:2.176ex;" alt="{\textstyle \mu }" loading="lazy"> of the highest degree <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\textstyle d}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\textstyle d}</annotation>

</semantics>

</math><img src="./252135f29da0e9f9e130ff2d53be5df2f7044d99.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.216ex; height:2.176ex;" alt="{\textstyle d}" loading="lazy"> in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\textstyle p_{x}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\textstyle p_{x}}</annotation>

</semantics>

</math><img src="./f8166b00c5a2a66ea1bcb0c28077e288f1cca352.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:2.431ex; height:2.009ex;" alt="{\textstyle p_{x}}" loading="lazy"> and sum all the evaluation points of the polynomial where all variables in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\textstyle \mu }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\textstyle \mu }</annotation>

</semantics>

</math><img src="./259577540a13444806174d5a1ae7662974f58085.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:1.402ex; height:2.176ex;" alt="{\textstyle \mu }" loading="lazy"> have the values 0 or 1, and all the other variables have value 0, you get the value of the coefficient (0 or 1) of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\textstyle \mu }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\textstyle \mu }</annotation>

</semantics>

</math><img src="./259577540a13444806174d5a1ae7662974f58085.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:1.402ex; height:2.176ex;" alt="{\textstyle \mu }" loading="lazy"> in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\textstyle p_{x}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\textstyle p_{x}}</annotation>

</semantics>

</math><img src="./f8166b00c5a2a66ea1bcb0c28077e288f1cca352.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:2.431ex; height:2.009ex;" alt="{\textstyle p_{x}}" loading="lazy"> (There are <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\textstyle 2^{d}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\textstyle 2^{d}}</annotation>

</semantics>

</math><img src="./a10e09e3d92066b164fdc49873c35a1c4a060364.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.254ex; height:2.676ex;" alt="{\textstyle 2^{d}}" loading="lazy"> such points). This is due to the fact that all lower monomial divisors of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\textstyle \mu }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\textstyle \mu }</annotation>

</semantics>

</math><img src="./259577540a13444806174d5a1ae7662974f58085.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:1.402ex; height:2.176ex;" alt="{\textstyle \mu }" loading="lazy"> appears an even number of time in the sum, and only <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\textstyle \mu }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\textstyle \mu }</annotation>

</semantics>

</math><img src="./259577540a13444806174d5a1ae7662974f58085.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:1.402ex; height:2.176ex;" alt="{\textstyle \mu }" loading="lazy"> appears once.

To take into account the possibility of errors, you can also remark that you can fix the value of other variables to any value. So instead of doing the sum only once for other variables not in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\textstyle \mu }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\textstyle \mu }</annotation>

</semantics>

</math><img src="./259577540a13444806174d5a1ae7662974f58085.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:1.402ex; height:2.176ex;" alt="{\textstyle \mu }" loading="lazy"> with 0 value, you do it <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\textstyle 2^{m-d}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\textstyle 2^{m-d}}</annotation>

</semantics>

</math><img src="./47e5c64a22bec38114716d27e530842a290266db.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:4.976ex; height:2.676ex;" alt="{\textstyle 2^{m-d}}" loading="lazy"> times for each fixed valuations of the other variables. If there is no error, all those sums should be equals to the value of the coefficient searched.

The algorithm consists here to take the majority of the answers as the value searched. If the minority is larger than the maximum number of errors possible, the decoding step fails knowing there are too many errors in the input code.

Once a coefficient is computed, if it's 1, update the code to remove the monomial <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\textstyle \mu }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\textstyle \mu }</annotation>

</semantics>

</math><img src="./259577540a13444806174d5a1ae7662974f58085.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:1.402ex; height:2.176ex;" alt="{\textstyle \mu }" loading="lazy"> from the input code and continue to next monomial, in reverse order of their degree.

<div class="mw-heading mw-heading4"><h4 id="Example_2">Example</h4></div>

Let's consider the previous example and start from the code. With <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\textstyle r=2,m=4}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\textstyle r=2,m=4}</annotation>

</semantics>

</math><img src="./6a9f137e8ad2152ece568316961288d33598a8d5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:12.645ex; height:2.509ex;" alt="{\textstyle r=2,m=4}" loading="lazy"> we can fix at most 1 error in the code.

Consider the input code as 1101 1110 0001 0110 (this is the previous code with one error).

We know the degree of the polynomial <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\textstyle p_{x}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\textstyle p_{x}}</annotation>

</semantics>

</math><img src="./f8166b00c5a2a66ea1bcb0c28077e288f1cca352.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:2.431ex; height:2.009ex;" alt="{\textstyle p_{x}}" loading="lazy"> is at most <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\textstyle r=2}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\textstyle r=2}</annotation>

</semantics>

</math><img src="./d300f60dffec92a7aba324cf2022ad14141a4e31.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.31ex; height:2.176ex;" alt="{\textstyle r=2}" loading="lazy">, we start by searching for monomial of degree 2.

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\textstyle \mu =X_{3}X_{4}}</annotation>

</semantics>

</math><img src="./9d045b214d49af8a8f07a601025634dd89664341.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.457ex; height:2.676ex;" alt="{\textstyle \mu =X_{3}X_{4}}" loading="lazy">

<ul><li>we start by looking for evaluation points with <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\textstyle X_{1}=0,X_{2}=0,X_{3}\in \{0,1\},X_{4}\in \{0,1\}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\textstyle X_{1}=0,X_{2}=0,X_{3}\in \{0,1\},X_{4}\in \{0,1\}}</annotation>

</semantics>

</math><img src="./a0011c59227e1506b81eb45291d0ee8dffe562b2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:40.587ex; height:2.843ex;" alt="{\textstyle X_{1}=0,X_{2}=0,X_{3}\in \{0,1\},X_{4}\in \{0,1\}}" loading="lazy">. In the code this is: 1101 1110 0001 0110. The first sum is 1 (odd number of 1).</li>

<li>we look for evaluation points with <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\textstyle X_{1}=0,X_{2}=1,X_{3}\in \{0,1\},X_{4}\in \{0,1\}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\textstyle X_{1}=0,X_{2}=1,X_{3}\in \{0,1\},X_{4}\in \{0,1\}}</annotation>

</semantics>

</math><img src="./f525134abd4fdf354134ca9f028d7d7598bbac41.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:40.587ex; height:2.843ex;" alt="{\textstyle X_{1}=0,X_{2}=1,X_{3}\in \{0,1\},X_{4}\in \{0,1\}}" loading="lazy">. In the code this is: 1101 1110 0001 0110. The second sum is 1.</li>

<li>we look for evaluation points with <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\textstyle X_{1}=1,X_{2}=0,X_{3}\in \{0,1\},X_{4}\in \{0,1\}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\textstyle X_{1}=1,X_{2}=0,X_{3}\in \{0,1\},X_{4}\in \{0,1\}}</annotation>

</semantics>

</math><img src="./d9a182c9c42e6533830d722a887771a985b6c018.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:40.587ex; height:2.843ex;" alt="{\textstyle X_{1}=1,X_{2}=0,X_{3}\in \{0,1\},X_{4}\in \{0,1\}}" loading="lazy">. In the code this is: 1101 1110 0001 0110. The third sum is 1.</li>

<li>we look for evaluation points with <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\textstyle X_{1}=1,X_{2}=1,X_{3}\in \{0,1\},X_{4}\in \{0,1\}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\textstyle X_{1}=1,X_{2}=1,X_{3}\in \{0,1\},X_{4}\in \{0,1\}}</annotation>

</semantics>

</math><img src="./9835c202a3eb9f0b10ad51bbc8dc2059ea70422b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:40.587ex; height:2.843ex;" alt="{\textstyle X_{1}=1,X_{2}=1,X_{3}\in \{0,1\},X_{4}\in \{0,1\}}" loading="lazy">. In the code this is: 1101 1110 0001 0110. The third sum is 0 (even number of 1).</li></ul></li></ul>

The four sums don't agree (so we know there is an error), but the minority report is not larger than the maximum number of error allowed (1), so we take the majority and the coefficient of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\textstyle \mu }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\textstyle \mu }</annotation>

</semantics>

</math><img src="./259577540a13444806174d5a1ae7662974f58085.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:1.402ex; height:2.176ex;" alt="{\textstyle \mu }" loading="lazy"> is 1.

We remove <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\textstyle \mu }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\textstyle \mu }</annotation>

</semantics>

</math><img src="./259577540a13444806174d5a1ae7662974f58085.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:1.402ex; height:2.176ex;" alt="{\textstyle \mu }" loading="lazy"> from the code before continue : code : 1101 1110 0001 0110, valuation of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\textstyle \mu }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\textstyle \mu }</annotation>

</semantics>

</math><img src="./259577540a13444806174d5a1ae7662974f58085.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:1.402ex; height:2.176ex;" alt="{\textstyle \mu }" loading="lazy"> is 0001000100010001, the new code is 1100 1111 0000 0111

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\textstyle \mu =X_{2}X_{4}}</annotation>

</semantics>

</math><img src="./230a5661541a639b1627e4bdde4fba825d00e67d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.457ex; height:2.676ex;" alt="{\textstyle \mu =X_{2}X_{4}}" loading="lazy">

One error detected, coefficient is 0, no change to current code.

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\textstyle \mu =X_{1}X_{4}}</annotation>

</semantics>

</math><img src="./85263692fd63d63297d4604baee7f1933ba59306.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.457ex; height:2.676ex;" alt="{\textstyle \mu =X_{1}X_{4}}" loading="lazy">

One error detected, coefficient is 0, no change to current code.

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\textstyle \mu =X_{2}X_{3}}</annotation>

</semantics>

</math><img src="./100a8512570031296c0aa4b9f55e6c2291d943fc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.457ex; height:2.676ex;" alt="{\textstyle \mu =X_{2}X_{3}}" loading="lazy">

One error detected, coefficient is 1, valuation of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\textstyle \mu }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\textstyle \mu }</annotation>

</semantics>

</math><img src="./259577540a13444806174d5a1ae7662974f58085.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:1.402ex; height:2.176ex;" alt="{\textstyle \mu }" loading="lazy"> is 0000 0011 0000 0011, current code is now 1100 1100 0000 0100.

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\textstyle \mu =X_{1}X_{3}}</annotation>

</semantics>

</math><img src="./242af7c5f59af747f62aa76f0ef34d27444c625b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.457ex; height:2.676ex;" alt="{\textstyle \mu =X_{1}X_{3}}" loading="lazy">

One error detected, coefficient is 1, valuation of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\textstyle \mu }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\textstyle \mu }</annotation>

</semantics>

</math><img src="./259577540a13444806174d5a1ae7662974f58085.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:1.402ex; height:2.176ex;" alt="{\textstyle \mu }" loading="lazy"> is 0000 0000 0011 0011, current code is now 1100 1100 0011 0111.

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\textstyle \mu =X_{1}X_{2}}</annotation>

</semantics>

</math><img src="./0ed2225935a64af3b0749fbe5f23a2db0c8107b2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.457ex; height:2.676ex;" alt="{\textstyle \mu =X_{1}X_{2}}" loading="lazy">

One error detected, coefficient is 0, no change to current code.

We know now all coefficient of degree 2 for the polynomial, we can start mononials of degree 1. Notice that for each next degree, there are twice as much sums, and each sums is half smaller.

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\textstyle \mu =X_{4}}</annotation>

</semantics>

</math><img src="./e28329a2935ada382965cf712af7ea6ede4db0ce.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.479ex; height:2.676ex;" alt="{\textstyle \mu =X_{4}}" loading="lazy">

One error detected, coefficient is 0, no change to current code.

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\textstyle \mu =X_{3}}</annotation>

</semantics>

</math><img src="./af3208f9a478dc8653c79a86c545a7635e57fac6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.479ex; height:2.676ex;" alt="{\textstyle \mu =X_{3}}" loading="lazy">

One error detected, coefficient is 1, valuation of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\textstyle \mu }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\textstyle \mu }</annotation>

</semantics>

</math><img src="./259577540a13444806174d5a1ae7662974f58085.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:1.402ex; height:2.176ex;" alt="{\textstyle \mu }" loading="lazy"> is 0011 0011 0011 0011, current code is now 1111 1111 0000 0100.

Then we'll find 0 for <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\textstyle \mu =X_{2}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\textstyle \mu =X_{2}}</annotation>

</semantics>

</math><img src="./d89c67b36651235f954e9a3aebfa15d9fe1dd0a0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.479ex; height:2.676ex;" alt="{\textstyle \mu =X_{2}}" loading="lazy">, 1 for <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\textstyle \mu =X_{1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\textstyle \mu =X_{1}}</annotation>

</semantics>

</math><img src="./66ae85cbbd308e2305e7205c4a2c91a513e209de.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.479ex; height:2.676ex;" alt="{\textstyle \mu =X_{1}}" loading="lazy"> and the current code become 1111 1111 1111 1011.

For the degree 0, we have 16 sums of only 1 bit. The minority is still of size 1, and we found <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\textstyle p_{x}=1+X_{1}+X_{3}+X_{1}X_{3}+X_{2}X_{3}+X_{3}X_{4}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\textstyle p_{x}=1+X_{1}+X_{3}+X_{1}X_{3}+X_{2}X_{3}+X_{3}X_{4}}</annotation>

</semantics>

</math><img src="./ce25ca4cea6e65e5d7c4e23853f879f09841d433.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:44.722ex; height:2.509ex;" alt="{\textstyle p_{x}=1+X_{1}+X_{3}+X_{1}X_{3}+X_{2}X_{3}+X_{3}X_{4}}" loading="lazy"> and the corresponding initial word 1 1010 010101

<div class="mw-heading mw-heading3"><h3 id="Generalization_to_larger_alphabets_via_low-degree_polynomials">Generalization to larger alphabets via low-degree polynomials</h3></div>

Using low-degree polynomials over a finite field <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbb {F} }">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbb {F} }</annotation>

</semantics>

</math><img src="./573f72afae7df709959ab1a58cd643743466a187.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.42ex; height:2.176ex;" alt="{\displaystyle \mathbb {F} }" loading="lazy"> of size <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle q}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle q}</annotation>

</semantics>

</math><img src="./06809d64fa7c817ffc7e323f85997f783dbdf71d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.07ex; height:2.009ex;" alt="{\displaystyle q}" loading="lazy">, it is possible to extend the definition of Reed–Muller codes to alphabets of size <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle q}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle q}</annotation>

</semantics>

</math><img src="./06809d64fa7c817ffc7e323f85997f783dbdf71d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.07ex; height:2.009ex;" alt="{\displaystyle q}" loading="lazy">. Let <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m}</annotation>

</semantics>

</math><img src="./0a07d98bb302f3856cbabc47b2b9016692e3f7bc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.04ex; height:1.676ex;" alt="{\displaystyle m}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle d}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle d}</annotation>

</semantics>

</math><img src="./e85ff03cbe0c7341af6b982e47e9f90d235c66ab.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.216ex; height:2.176ex;" alt="{\displaystyle d}" loading="lazy"> be positive integers, where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m}</annotation>

</semantics>

</math><img src="./0a07d98bb302f3856cbabc47b2b9016692e3f7bc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.04ex; height:1.676ex;" alt="{\displaystyle m}" loading="lazy"> should be thought of as larger than <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle d}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle d}</annotation>

</semantics>

</math><img src="./e85ff03cbe0c7341af6b982e47e9f90d235c66ab.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.216ex; height:2.176ex;" alt="{\displaystyle d}" loading="lazy">. To encode a message <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\textstyle x\in \mathbb {F} ^{k}}">

<msup>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\textstyle x\in \mathbb {F} ^{k}}</annotation>

</semantics>

</math><img src="./428bc92788f93df728c3ee6bf1e2e393d25b4a63.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6.679ex; height:2.676ex;" alt="{\textstyle x\in \mathbb {F} ^{k}}" loading="lazy"> of width <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k=\textstyle {\binom {m+d}{m}}}">

<mrow>

</mrow>

<mrow>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k=\textstyle {\binom {m+d}{m}}}</annotation>

</semantics>

</math><img src="./845170ce34e8f34ffff452f6ac893437327cd6e8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:10.021ex; height:3.509ex;" alt="{\displaystyle k=\textstyle {\binom {m+d}{m}}}" loading="lazy">, the message is again interpreted as an <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m}</annotation>

</semantics>

</math><img src="./0a07d98bb302f3856cbabc47b2b9016692e3f7bc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.04ex; height:1.676ex;" alt="{\displaystyle m}" loading="lazy">-variate polynomial <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p_{x}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p_{x}}</annotation>

</semantics>

</math><img src="./5a5055ed65713825b48aa6ee05118c072e6f026a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:2.431ex; height:2.009ex;" alt="{\displaystyle p_{x}}" loading="lazy"> of total degree at most <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle d}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle d}</annotation>

</semantics>

</math><img src="./e85ff03cbe0c7341af6b982e47e9f90d235c66ab.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.216ex; height:2.176ex;" alt="{\displaystyle d}" loading="lazy"> and with coefficient from <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbb {F} }">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbb {F} }</annotation>

</semantics>

</math><img src="./573f72afae7df709959ab1a58cd643743466a187.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.42ex; height:2.176ex;" alt="{\displaystyle \mathbb {F} }" loading="lazy">. Such a polynomial indeed has <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \textstyle {\binom {m+d}{m}}}">

<mrow>

</mrow>

<mrow>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \textstyle {\binom {m+d}{m}}}</annotation>

</semantics>

</math><img src="./328864d8fbce032730ea5d52b5af1172adee116e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:5.711ex; height:3.509ex;" alt="{\displaystyle \textstyle {\binom {m+d}{m}}}" loading="lazy"> coefficients. The Reed–Muller encoding of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x}</annotation>

</semantics>

</math><img src="./87f9e315fd7e2ba406057a97300593c4802b53e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}" loading="lazy"> is the list of all evaluations of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p_{x}(a)}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p_{x}(a)}</annotation>

</semantics>

</math><img src="./a064d11d0464a88d6ebf46bb94de1798334a9945.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; margin-left: -0.089ex; width:5.47ex; height:2.843ex;" alt="{\displaystyle p_{x}(a)}" loading="lazy"> over all <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a\in \mathbb {F} ^{m}}">

<msup>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a\in \mathbb {F} ^{m}}</annotation>

</semantics>

</math><img src="./2d1f9fc0182ed263f4d0c30a68b303b021574563.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:7.166ex; height:2.343ex;" alt="{\displaystyle a\in \mathbb {F} ^{m}}" loading="lazy">. Thus the block length is <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n=q^{m}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n=q^{m}}</annotation>

</semantics>

</math><img src="./cff9fd42a37099194ee008daed0b11f22c443622.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:7.248ex; height:2.676ex;" alt="{\displaystyle n=q^{m}}" loading="lazy">.

<div class="mw-heading mw-heading2"><h2 id="Description_using_a_generator_matrix">Description using a generator matrix</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .ambox{border:1px solid #a2a9b1;border-left:10px solid #36c;background-color:#fbfbfb;box-sizing:border-box}.mw-parser-output .ambox+link+.ambox,.mw-parser-output .ambox+link+style+.ambox,.mw-parser-output .ambox+link+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+style+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+link+.ambox{margin-top:-1px}html body.mediawiki .mw-parser-output .ambox.mbox-small-left{margin:4px 1em 4px 0;overflow:hidden;width:238px;border-collapse:collapse;font-size:88%;line-height:1.25em}.mw-parser-output .ambox-speedy{border-left:10px solid #b32424;background-color:#fee7e6}.mw-parser-output .ambox-delete{border-left:10px solid #b32424}.mw-parser-output .ambox-content{border-left:10px solid #f28500}.mw-parser-output .ambox-style{border-left:10px solid #fc3}.mw-parser-output .ambox-move{border-left:10px solid #9932cc}.mw-parser-output .ambox-protection{border-left:10px solid #a2a9b1}.mw-parser-output .ambox .mbox-text{border:none;padding:0.25em 0.5em;width:100%}.mw-parser-output .ambox .mbox-image{border:none;padding:2px 0 2px 0.5em;text-align:center}.mw-parser-output .ambox .mbox-imageright{border:none;padding:2px 0.5em 2px 0;text-align:center}.mw-parser-output .ambox .mbox-empty-cell{border:none;padding:0;width:1px}.mw-parser-output .ambox .mbox-image-div{width:52px}@media(min-width:720px){.mw-parser-output .ambox{margin:0 10%}}@media print{body.ns-0 .mw-parser-output .ambox{display:none!important}}

/* end https://en.wikipedia.org/ */

</style>

A <a href="Generator_matrix" title="Generator matrix">generator matrix</a> for a Reed–Muller code RM(r, m) of length N = 2m can be constructed as follows. Let us write the set of all m-dimensional binary vectors as:

</mrow>

</mrow>

</mrow>

</msubsup>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle X=\mathbb {F} _{2}^{m}=\{x_{1},\ldots ,x_{N}\}.}</annotation>

</semantics>

</math><img src="./475f40e2c1237ca6976031d41a91a82fe75fa3c3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:24.827ex; height:2.843ex;" alt="{\displaystyle X=\mathbb {F} _{2}^{m}=\{x_{1},\ldots ,x_{N}\}.}" loading="lazy"></dd></dl>

We define in N-dimensional space <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbb {F} _{2}^{N}}">

</mrow>

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbb {F} _{2}^{N}}</annotation>

</semantics>

</math><img src="./15edca23e68c67a7ae4e803c11e7149c47c1e9b7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:3.112ex; height:3.176ex;" alt="{\displaystyle \mathbb {F} _{2}^{N}}" loading="lazy"> the <a href="Indicator_vector" title="Indicator vector">indicator vectors</a>

<msub>

</mrow>

</mrow>

</msub>

</mrow>

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbb {I} _{A}\in \mathbb {F} _{2}^{N}}</annotation>

</semantics>

</math><img src="./b3d2caf2a38e17656bbe317e7b2811d4d0d6c72f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.322ex; height:3.176ex;" alt="{\displaystyle \mathbb {I} _{A}\in \mathbb {F} _{2}^{N}}" loading="lazy"></dd></dl>

on subsets <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A\subset X}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A\subset X}</annotation>

</semantics>

</math><img src="./826569be03f873b81cdc6f12637ef5520c369d21.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6.822ex; height:2.176ex;" alt="{\displaystyle A\subset X}" loading="lazy"> by:

<msub>

<mrow>

<msub>

</mrow>

</mrow>

</msub>

</mrow>

</mrow>

</msub>

<mrow>

<mtr>

<mtd>

</mtd>

<mtd>

</mstyle>

</mrow>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

<mtext> otherwise</mtext>

</mstyle>

</mrow>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \left(\mathbb {I} _{A}\right)_{i}={\begin{cases}1&{\mbox{ if }}x_{i}\in A\\0&{\mbox{ otherwise}}\\\end{cases}}}</annotation>

</semantics>

</math><img src="./9ae4fb893fc7510d8b7c6697498ea08e11560128.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:24.214ex; height:6.176ex;" alt="{\displaystyle \left(\mathbb {I} _{A}\right)_{i}={\begin{cases}1&{\mbox{ if }}x_{i}\in A\\0&{\mbox{ otherwise}}\\\end{cases}}}" loading="lazy"></dd></dl>

together with, also in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbb {F} _{2}^{N}}">

</mrow>

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbb {F} _{2}^{N}}</annotation>

</semantics>

</math><img src="./15edca23e68c67a7ae4e803c11e7149c47c1e9b7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:3.112ex; height:3.176ex;" alt="{\displaystyle \mathbb {F} _{2}^{N}}" loading="lazy">, the binary operation

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle w\wedge z=(w_{1}\cdot z_{1},\ldots ,w_{N}\cdot z_{N}),}</annotation>

</semantics>

</math><img src="./167b56bdd76c88f3b42b8a09c9841245c5bf898e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:30.408ex; height:2.843ex;" alt="{\displaystyle w\wedge z=(w_{1}\cdot z_{1},\ldots ,w_{N}\cdot z_{N}),}" loading="lazy"></dd></dl>

referred to as the wedge product (not to be confused with the <a href="Wedge_product" class="mw-redirect" title="Wedge product">wedge product</a> defined in exterior algebra). Here, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle w=(w_{1},w_{2},\ldots ,w_{N})}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle w=(w_{1},w_{2},\ldots ,w_{N})}</annotation>

</semantics>

</math><img src="./d3d9fbdfbdf26046ad632619bfbcd53b2590883e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:21.576ex; height:2.843ex;" alt="{\displaystyle w=(w_{1},w_{2},\ldots ,w_{N})}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle z=(z_{1},z_{2},\ldots ,z_{N})}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle z=(z_{1},z_{2},\ldots ,z_{N})}</annotation>

</semantics>

</math><img src="./6dac951eb848e5e16fe7a5f500e8274d4eacc6dd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:19.251ex; height:2.843ex;" alt="{\displaystyle z=(z_{1},z_{2},\ldots ,z_{N})}" loading="lazy"> are points in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbb {F} _{2}^{N}}">

</mrow>

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbb {F} _{2}^{N}}</annotation>

</semantics>

</math><img src="./15edca23e68c67a7ae4e803c11e7149c47c1e9b7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:3.112ex; height:3.176ex;" alt="{\displaystyle \mathbb {F} _{2}^{N}}" loading="lazy"> (N-dimensional binary vectors), and the operation <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \cdot }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \cdot }</annotation>

</semantics>

</math><img src="./ba2c023bad1bd39ed49080f729cbf26bc448c9ba.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: 0.439ex; margin-bottom: -0.61ex; width:0.647ex; height:1.176ex;" alt="{\displaystyle \cdot }" loading="lazy"> is the usual multiplication in the field <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbb {F} _{2}}">

<msub>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbb {F} _{2}}</annotation>

</semantics>

</math><img src="./fde97f1e971e76227cd0aac645b7b0901d7b668d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.475ex; height:2.509ex;" alt="{\displaystyle \mathbb {F} _{2}}" loading="lazy">.

</mrow>

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbb {F} _{2}^{m}}</annotation>

</semantics>

</math><img src="./0b4822a135201cbc45180f16312b9f1008bae3b6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:3.095ex; height:2.843ex;" alt="{\displaystyle \mathbb {F} _{2}^{m}}" loading="lazy"> is an m-dimensional vector space over the field <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbb {F} _{2}}">

<msub>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbb {F} _{2}}</annotation>

</semantics>

</math><img src="./fde97f1e971e76227cd0aac645b7b0901d7b668d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.475ex; height:2.509ex;" alt="{\displaystyle \mathbb {F} _{2}}" loading="lazy">, so it is possible to write

<msub>

</mrow>

</mrow>

</msub>

<msup>

</mrow>

</msup>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (\mathbb {F} _{2})^{m}=\{(y_{m},\ldots ,y_{1})\mid y_{i}\in \mathbb {F} _{2}\}.}</annotation>

</semantics>

</math><img src="./96b9aaddd92eeab07796b8b0ede9698676e73226.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:33.216ex; height:2.843ex;" alt="{\displaystyle (\mathbb {F} _{2})^{m}=\{(y_{m},\ldots ,y_{1})\mid y_{i}\in \mathbb {F} _{2}\}.}" loading="lazy">

We define in N-dimensional space <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbb {F} _{2}^{N}}">

</mrow>

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbb {F} _{2}^{N}}</annotation>

</semantics>

</math><img src="./15edca23e68c67a7ae4e803c11e7149c47c1e9b7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:3.112ex; height:3.176ex;" alt="{\displaystyle \mathbb {F} _{2}^{N}}" loading="lazy"> the following vectors with length <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N:v_{0}=(1,1,\ldots ,1)}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N:v_{0}=(1,1,\ldots ,1)}</annotation>

</semantics>

</math><img src="./8c663e525a1430dd7d14e74e0bfc34ffc9a89390.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:20.79ex; height:2.843ex;" alt="{\displaystyle N:v_{0}=(1,1,\ldots ,1)}" loading="lazy"> and

<msub>

</mrow>

</msub>

<msub>

</mrow>

<msub>

</mrow>

</msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle v_{i}=\mathbb {I} _{H_{i}},}</annotation>

</semantics>

</math><img src="./c088bbab963ead219e33f28ca986c20186ba020b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:8.8ex; height:2.843ex;" alt="{\displaystyle v_{i}=\mathbb {I} _{H_{i}},}" loading="lazy"></dd></dl>

where 1 ≤ i ≤ m and the Hi are <a href="Hyperplane" title="Hyperplane">hyperplanes</a> in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (\mathbb {F} _{2})^{m}}">

<msub>

</mrow>

</mrow>

</msub>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (\mathbb {F} _{2})^{m}}</annotation>

</semantics>

</math><img src="./f306ca24de716be97fbbe460422e434ec18eb94d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.959ex; height:2.843ex;" alt="{\displaystyle (\mathbb {F} _{2})^{m}}" loading="lazy"> (with dimension m − 1):

<msub>

</mrow>

</msub>

<msub>

</mrow>

</mrow>

</msub>

<msup>

</mrow>

</msup>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle H_{i}=\{y\in (\mathbb {F} _{2})^{m}\mid y_{i}=0\}.}</annotation>

</semantics>

</math><img src="./4da1f6c3ef193c9b921682bbd56329217eefd89b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:26.893ex; height:2.843ex;" alt="{\displaystyle H_{i}=\{y\in (\mathbb {F} _{2})^{m}\mid y_{i}=0\}.}" loading="lazy"></dd></dl>

<div class="mw-heading mw-heading3"><h3 id="The_generator_matrix">The generator matrix</h3></div>

The Reed–Muller RM(r, m) code of order r and length N = 2m is the code generated by v0 and the wedge products of up to r of the vi, 1 ≤ i ≤ m (where by convention a wedge product of fewer than one vector is the identity for the operation). In other words, we can build a generator matrix for the RM(r, m) code, using vectors and their wedge product permutations up to r at a time <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {v_{0},v_{1},\ldots ,v_{n},\ldots ,(v_{i_{1}}\wedge v_{i_{2}}),\ldots (v_{i_{1}}\wedge v_{i_{2}}\ldots \wedge v_{i_{r}})}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

<msub>

</mrow>

</msub>

</mrow>

</msub>

<msub>

<msub>

</mrow>

</msub>

</mrow>

</msub>

<msub>

<msub>

</mrow>

</msub>

</mrow>

</msub>

<msub>

<msub>

</mrow>

</msub>

</mrow>

</msub>

<msub>

<msub>

</mrow>

</msub>

</mrow>

</msub>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {v_{0},v_{1},\ldots ,v_{n},\ldots ,(v_{i_{1}}\wedge v_{i_{2}}),\ldots (v_{i_{1}}\wedge v_{i_{2}}\ldots \wedge v_{i_{r}})}}</annotation>

</semantics>

</math><img src="./ecb7284dbb9098f7d1757b04c7cd3cd066a82a36.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:50.45ex; height:3.009ex;" alt="{\displaystyle {v_{0},v_{1},\ldots ,v_{n},\ldots ,(v_{i_{1}}\wedge v_{i_{2}}),\ldots (v_{i_{1}}\wedge v_{i_{2}}\ldots \wedge v_{i_{r}})}}" loading="lazy">, as the rows of the generator matrix, where 1 ≤ ik ≤ m.

<div class="mw-heading mw-heading3"><h3 id="Example_1">Example 1</h3></div>

Let m = 3. Then N = 8, and

</mrow>

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle X=\mathbb {F} _{2}^{3}=\{(0,0,0),(0,0,1),(0,1,0)\ldots ,(1,1,1)\},}</annotation>

</semantics>

</math><img src="./e97e4a7e254aed6b2b43cb7ebc76be25b8f20c70.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:49.681ex; height:3.176ex;" alt="{\displaystyle X=\mathbb {F} _{2}^{3}=\{(0,0,0),(0,0,1),(0,1,0)\ldots ,(1,1,1)\},}" loading="lazy"></dd></dl>

and

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}v_{0}&=(1,1,1,1,1,1,1,1)\\[2pt]v_{1}&=(1,0,1,0,1,0,1,0)\\[2pt]v_{2}&=(1,1,0,0,1,1,0,0)\\[2pt]v_{3}&=(1,1,1,1,0,0,0,0).\end{aligned}}}</annotation>

</semantics>

</math><img src="./d4824ef0b765d3569599515d7b3cd9158892a5e0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -6.338ex; width:25.025ex; height:13.843ex;" alt="{\displaystyle {\begin{aligned}v_{0}&=(1,1,1,1,1,1,1,1)\\[2pt]v_{1}&=(1,0,1,0,1,0,1,0)\\[2pt]v_{2}&=(1,1,0,0,1,1,0,0)\\[2pt]v_{3}&=(1,1,1,1,0,0,0,0).\end{aligned}}}" loading="lazy"></dd></dl>

The RM(1,3) code is generated by the set

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \{v_{0},v_{1},v_{2},v_{3}\},\,}</annotation>

</semantics>

</math><img src="./bf53cd0b1ec2e5804414cbad529d2d2cf8f4ff73.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:15.188ex; height:2.843ex;" alt="{\displaystyle \{v_{0},v_{1},v_{2},v_{3}\},\,}" loading="lazy"></dd></dl>

or more explicitly by the rows of the matrix:

<mrow>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{pmatrix}1&1&1&1&1&1&1&1\\1&0&1&0&1&0&1&0\\1&1&0&0&1&1&0&0\\1&1&1&1&0&0&0&0\end{pmatrix}}}</annotation>

</semantics>

</math><img src="./4f47ad9f34a9adf9432f80d478ba6d2d422e8765.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -5.671ex; width:30.376ex; height:12.509ex;" alt="{\displaystyle {\begin{pmatrix}1&1&1&1&1&1&1&1\\1&0&1&0&1&0&1&0\\1&1&0&0&1&1&0&0\\1&1&1&1&0&0&0&0\end{pmatrix}}}" loading="lazy"></dd></dl>

<div class="mw-heading mw-heading3"><h3 id="Example_2_2">Example 2</h3></div>

The RM(2,3) code is generated by the set:

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \{v_{0},v_{1},v_{2},v_{3},v_{1}\wedge v_{2},v_{1}\wedge v_{3},v_{2}\wedge v_{3}\}}</annotation>

</semantics>

</math><img src="./a1ce1e89b1e50c159d560c29617d41123755d4b2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:38.095ex; height:2.843ex;" alt="{\displaystyle \{v_{0},v_{1},v_{2},v_{3},v_{1}\wedge v_{2},v_{1}\wedge v_{3},v_{2}\wedge v_{3}\}}" loading="lazy"></dd></dl>

or more explicitly by the rows of the matrix:

<mrow>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{pmatrix}1&1&1&1&1&1&1&1\\1&0&1&0&1&0&1&0\\1&1&0&0&1&1&0&0\\1&1&1&1&0&0&0&0\\1&0&0&0&1&0&0&0\\1&0&1&0&0&0&0&0\\1&1&0&0&0&0&0&0\\\end{pmatrix}}}</annotation>

</semantics>

</math><img src="./4cd9bf0c31131a5cac5b0b87754f009bcdfc8e11.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -10.671ex; width:30.376ex; height:22.343ex;" alt="{\displaystyle {\begin{pmatrix}1&1&1&1&1&1&1&1\\1&0&1&0&1&0&1&0\\1&1&0&0&1&1&0&0\\1&1&1&1&0&0&0&0\\1&0&0&0&1&0&0&0\\1&0&1&0&0&0&0&0\\1&1&0&0&0&0&0&0\\\end{pmatrix}}}" loading="lazy"></dd></dl>

<div class="mw-heading mw-heading3"><h3 id="Properties">Properties</h3></div>

The following properties hold:

<ol><li>The set of all possible wedge products of up to m of the vi form a basis for <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbb {F} _{2}^{N}}">

</mrow>

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbb {F} _{2}^{N}}</annotation>

</semantics>

</math><img src="./15edca23e68c67a7ae4e803c11e7149c47c1e9b7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:3.112ex; height:3.176ex;" alt="{\displaystyle \mathbb {F} _{2}^{N}}" loading="lazy">.</li>

</mrow>

</mrow>

</munderover>

<mrow>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \sum _{s=0}^{r}{m \choose s}.}</annotation>

</semantics>

</math><img src="./72b92df6ab753cb2243d41efcbf8cc81acbd3d8e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.005ex; width:9.85ex; height:6.843ex;" alt="{\displaystyle \sum _{s=0}^{r}{m \choose s}.}" loading="lazy"></dd></dl></li>

<li>RM (r, m) = RM (r, m − 1) | RM (r − 1, m − 1) where '|' denotes the <a href="Bar_product_(coding_theory)" class="mw-redirect" title="Bar product (coding theory)">bar product</a> of two codes.</li>

<li>RM (r, m) has minimum <a href="Hamming_weight" title="Hamming weight">Hamming weight</a> 2m − r.</li></ol>

<div class="mw-heading mw-heading4"><h4 id="Proof">Proof</h4></div>

<div><ol><li>There are

</mrow>

</mrow>

</munderover>

<mrow>

</mrow>

</mfrac>

</mrow>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \sum _{s=0}^{m}{m \choose s}=2^{m}=N}</annotation>

</semantics>

</math><img src="./e58aad7ed3123ba2ec5e1234a1e468f6baa7239b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.005ex; width:20.302ex; height:6.843ex;" alt="{\displaystyle \sum _{s=0}^{m}{m \choose s}=2^{m}=N}" loading="lazy"></dd></dl></dd></dl>

such vectors and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbb {F} _{2}^{N}}">

</mrow>

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbb {F} _{2}^{N}}</annotation>

</semantics>

</math><img src="./15edca23e68c67a7ae4e803c11e7149c47c1e9b7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:3.112ex; height:3.176ex;" alt="{\displaystyle \mathbb {F} _{2}^{N}}" loading="lazy"> have dimension N so it is sufficient to check that the N vectors span; equivalently it is sufficient to check that <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathrm {RM} (m,m)=\mathbb {F} _{2}^{N}}">

</mrow>

</mrow>

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathrm {RM} (m,m)=\mathbb {F} _{2}^{N}}</annotation>

</semantics>

</math><img src="./3532371705183c9df9620a2aa662eb3776749bda.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:16.976ex; height:3.176ex;" alt="{\displaystyle \mathrm {RM} (m,m)=\mathbb {F} _{2}^{N}}" loading="lazy">.

Let x be a binary vector of length m, an element of X. Let (x)i denote the ith element of x. Define

<msub>

</mrow>

</msub>

<mrow>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

</mrow>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

</mrow>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y_{i}={\begin{cases}v_{i}&{\text{ if }}(x)_{i}=0\\v_{0}+v_{i}&{\text{ if }}(x)_{i}=1\\\end{cases}}}</annotation>

</semantics>

</math><img src="./372d078e891874a86df08469cdd5a1b195272b40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:27.524ex; height:6.176ex;" alt="{\displaystyle y_{i}={\begin{cases}v_{i}&{\text{ if }}(x)_{i}=0\\v_{0}+v_{i}&{\text{ if }}(x)_{i}=1\\\end{cases}}}" loading="lazy"></dd></dl></dd></dl>

where 1 ≤ i ≤m.

Then <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbb {I} _{\{x\}}=y_{1}\wedge \cdots \wedge y_{m}}">

<msub>

</mrow>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbb {I} _{\{x\}}=y_{1}\wedge \cdots \wedge y_{m}}</annotation>

</semantics>

</math><img src="./223ae7d824e11a17ac998d5b16f1022e166a9273.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.171ex; width:19.716ex; height:3.009ex;" alt="{\displaystyle \mathbb {I} _{\{x\}}=y_{1}\wedge \cdots \wedge y_{m}}" loading="lazy">

Expansion via the distributivity of the wedge product gives <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbb {I} _{\{x\}}\in \mathrm {RM} (m,m)}">

<msub>

</mrow>

</mrow>

</msub>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbb {I} _{\{x\}}\in \mathrm {RM} (m,m)}</annotation>

</semantics>

</math><img src="./b6e1ca58c1977bf20cc68d842addbfab486f3314.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.171ex; width:17.327ex; height:3.176ex;" alt="{\displaystyle \mathbb {I} _{\{x\}}\in \mathrm {RM} (m,m)}" loading="lazy">. Then since the vectors <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \{\mathbb {I} _{\{x\}}\mid x\in X\}}">

<msub>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \{\mathbb {I} _{\{x\}}\mid x\in X\}}</annotation>

</semantics>

</math><img src="./aae4d575700f44cac2e35dd56579e0f9a1438d6c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.171ex; width:14.134ex; height:3.176ex;" alt="{\displaystyle \{\mathbb {I} _{\{x\}}\mid x\in X\}}" loading="lazy"> span <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbb {F} _{2}^{N}}">

</mrow>

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbb {F} _{2}^{N}}</annotation>

</semantics>

</math><img src="./15edca23e68c67a7ae4e803c11e7149c47c1e9b7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:3.112ex; height:3.176ex;" alt="{\displaystyle \mathbb {F} _{2}^{N}}" loading="lazy"> we have <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathrm {RM} (m,n)=\mathbb {F} _{2}^{N}}">

</mrow>

</mrow>

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathrm {RM} (m,n)=\mathbb {F} _{2}^{N}}</annotation>

</semantics>

</math><img src="./aa3b6c1a09ffd3a0af4221d12f637a9f4d35dcfd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:16.33ex; height:3.176ex;" alt="{\displaystyle \mathrm {RM} (m,n)=\mathbb {F} _{2}^{N}}" loading="lazy">.</li><li>By 1, all such wedge products must be linearly independent, so the rank of RM(r, m) must simply be the number of such vectors.</li><li>Omitted.</li><li>By induction.

<dl><dd>The RM(0, m) code is the repetition code of length N =2m and weight N = 2m−0 = 2m−r. By 1 <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathrm {RM} (m,n)=\mathbb {F} _{2}^{n}}">

</mrow>

</mrow>

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathrm {RM} (m,n)=\mathbb {F} _{2}^{n}}</annotation>

</semantics>

</math><img src="./15294e5508d2630739b6ad15e8b332b45bb03309.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:15.857ex; height:2.843ex;" alt="{\displaystyle \mathrm {RM} (m,n)=\mathbb {F} _{2}^{n}}" loading="lazy"> and has weight 1 = 20 = 2m−r.</dd></dl>

The article <a href="Bar_product_(coding_theory)" class="mw-redirect" title="Bar product (coding theory)">bar product (coding theory)</a> gives a proof that the weight of the bar product of two codes C1 , C2 is given by

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \min\{2w(C_{1}),w(C_{2})\}}</annotation>

</semantics>

</math><img src="./f980e7870a1abbf2582902ce4802bee31438bf04.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:20.776ex; height:2.843ex;" alt="{\displaystyle \min\{2w(C_{1}),w(C_{2})\}}" loading="lazy"></dd></dl></dd></dl>

<dl><dd>If 0 < r < m and if <div><ol style="list-style-type:lower-roman"><li>RM(r,m − 1) has weight 2m−1−r</li><li>RM(r − 1,m − 1) has weight 2m−1−(r−1) = 2m−r</li></ol></div></dd>

<dd>then the bar product has weight</dd></dl>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \min\{2\times 2^{m-1-r},2^{m-r}\}=2^{m-r}.}</annotation>

</semantics>

</math><img src="./62d67da54b2140d0d52c247ac638fdfda7ed56c6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:31.655ex; height:3.176ex;" alt="{\displaystyle \min\{2\times 2^{m-1-r},2^{m-r}\}=2^{m-r}.}" loading="lazy"></dd></dl></dd></dl></li></ol></div>

<div class="mw-heading mw-heading3"><h3 id="Decoding_RM_codes">Decoding RM codes</h3></div>

RM(r, m) codes can be decoded using <a href="Majority_logic_decoding" title="Majority logic decoding">majority logic decoding</a>. The basic idea of majority logic decoding is

to build several checksums for each received code word element. Since each of the different checksums must all

have the same value (i.e. the value of the message word element weight), we can use a majority logic decoding to decipher

the value of the message word element. Once each order of the polynomial is decoded, the received word is modified

accordingly by removing the corresponding codewords weighted by the decoded message contributions, up to the present stage.

So for a rth order RM code, we have to decode iteratively r+1, times before we arrive at the final

received code-word. Also, the values of the message bits are calculated through this scheme; finally we can calculate

the codeword by multiplying the message word (just decoded) with the generator matrix.

One clue if the decoding succeeded, is to have an all-zero modified received word, at the end of (r + 1)-stage decoding

through the majority logic decoding. This technique was proposed by Irving S. Reed, and is more general when applied

to other finite geometry codes.

<div class="mw-heading mw-heading2"><h2 id="Description_using_a_recursive_construction">Description using a recursive construction</h2></div>

A Reed–Muller code RM(r,m) exists for any integers <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m\geq 0}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m\geq 0}</annotation>

</semantics>

</math><img src="./b0d2d765e4cfd7adfbca9ae0e37e75a2811c0333.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:6.301ex; height:2.343ex;" alt="{\displaystyle m\geq 0}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 0\leq r\leq m}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 0\leq r\leq m}</annotation>

</semantics>

</math><img src="./a09f8aa9a054323a82b0ecefbc9af45bd14484fa.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:10.448ex; height:2.343ex;" alt="{\displaystyle 0\leq r\leq m}" loading="lazy">. RM(m, m) is defined as the universe (<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2^{m},2^{m},1}">

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 2^{m},2^{m},1}</annotation>

</semantics>

</math><img src="./bc2664e475f42f150032a4105baf0f603d6a3fc5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:8.905ex; height:2.676ex;" alt="{\displaystyle 2^{m},2^{m},1}" loading="lazy">) code. RM(−1,m) is defined as the trivial code (<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2^{m},0,\infty }">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 2^{m},0,\infty }</annotation>

</semantics>

</math><img src="./b2d2cd598a5896c86b551eec5f202dafb36bbfcc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:8.392ex; height:2.676ex;" alt="{\displaystyle 2^{m},0,\infty }" loading="lazy">). The remaining RM codes may be constructed from these elementary codes using the length-doubling construction

</mrow>

</mrow>

</mrow>

</mrow>

</mrow>

</mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathrm {RM} (r,m)=\{(\mathbf {u} ,\mathbf {u} +\mathbf {v} )\mid \mathbf {u} \in \mathrm {RM} (r,m-1),\mathbf {v} \in \mathrm {RM} (r-1,m-1)\}.}</annotation>

</semantics>

</math><img src="./27c1ffd12c916e3dac57f2c6acfb32b21917748a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:69.014ex; height:2.843ex;" alt="{\displaystyle \mathrm {RM} (r,m)=\{(\mathbf {u} ,\mathbf {u} +\mathbf {v} )\mid \mathbf {u} \in \mathrm {RM} (r,m-1),\mathbf {v} \in \mathrm {RM} (r-1,m-1)\}.}" loading="lazy"></dd></dl>

From this construction, RM(r,m) is a binary <a href="Linear_block_code" class="mw-redirect" title="Linear block code">linear block code</a> (n, k, d) with length n = 2m, dimension <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k(r,m)=k(r,m-1)+k(r-1,m-1)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k(r,m)=k(r,m-1)+k(r-1,m-1)}</annotation>

</semantics>

</math><img src="./8645eca8ea3d70e4e9c174fff1ceb64e2ce00e73.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:39.378ex; height:2.843ex;" alt="{\displaystyle k(r,m)=k(r,m-1)+k(r-1,m-1)}" loading="lazy"> and minimum distance <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle d=2^{m-r}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle d=2^{m-r}}</annotation>

</semantics>

</math><img src="./304a8c7ef0e90cd2920ed59f8a179f88a3c303f4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:9.172ex; height:2.509ex;" alt="{\displaystyle d=2^{m-r}}" loading="lazy"> for <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle r\geq 0}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle r\geq 0}</annotation>

</semantics>

</math><img src="./aa96c19954fcda2695f988938ccf091d2bc2bbae.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:5.31ex; height:2.343ex;" alt="{\displaystyle r\geq 0}" loading="lazy">. The <a href="Dual_code" title="Dual code">dual code</a> to RM(r,m) is RM(m-r-1,m). This shows that repetition and SPC codes are duals, biorthogonal and extended Hamming codes are duals and that codes with k = n/2 are self-dual.

<div class="mw-heading mw-heading2"><h2 id="Special_cases_of_Reed–Muller_codes">Special cases of Reed–Muller codes</h2></div>

<div class="mw-heading mw-heading3"><h3 id="Table_of_all_RM(r,m)_codes_for_m≤5">Table of all RM(r,m) codes for m≤5</h3></div>

All RM(r, m) codes with <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 0\leq m\leq 5}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 0\leq m\leq 5}</annotation>

</semantics>

</math><img src="./d8e26f9aacaa48896116d54b15b81d98c1080c09.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:10.562ex; height:2.343ex;" alt="{\displaystyle 0\leq m\leq 5}" loading="lazy"> and alphabet size 2 are displayed here, annotated with the standard [n,k,d] <a href="Block_code#Popular_notation" title="Block code">coding theory notation</a> for <a href="Block_code" title="Block code">block codes</a>. The code RM(r, m) is a <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \textstyle [2^{m},k,2^{m-r}]_{2}}">

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \textstyle [2^{m},k,2^{m-r}]_{2}}</annotation>

</semantics>

</math><img src="./d79ce1b070673df7e64fe61028308f56e44dc436.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:13.322ex; height:3.009ex;" alt="{\displaystyle \textstyle [2^{m},k,2^{m-r}]_{2}}" loading="lazy">-code, that is, it is a <a href="Linear_code" title="Linear code">linear code</a> over a <a href="Binary_set" class="mw-redirect" title="Binary set">binary alphabet</a>, has <a href="Block_code#The_block_length_n" title="Block code">block length</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \textstyle 2^{m}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \textstyle 2^{m}}</annotation>

</semantics>

</math><img src="./688f6c4efbff3d57daac042386bdfba9c108b2e7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.837ex; height:2.176ex;" alt="{\displaystyle \textstyle 2^{m}}" loading="lazy">, <a href="Block_code#The_message_length_k" title="Block code">message length</a> (or dimension) k, and <a href="Block_code#The_distance_d" title="Block code">minimum distance</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \textstyle 2^{m-r}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \textstyle 2^{m-r}}</annotation>

</semantics>

</math><img src="./adddc1267124b66f4fa658afb09da64e31dcb210.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:4.858ex; height:2.509ex;" alt="{\displaystyle \textstyle 2^{m-r}}" loading="lazy">.

<table>

<td>0

</td>

<td>1

</td>

<td>2

</td>

<td>3

</td>

<td>4

</td>

<td>5

</td>

<td>m

</td>

<td>

</td></tr>

<tr>

<td>

</td>

<td>

</td>

<td>

</td>

<td>

</td>

<td>

</td>

<td>Z

</td>

<td>RM(m,m) (2m, 2m, 1)

</td>

<td>universe codes

</td></tr>

<tr>

<td>

</td>

<td>

</td>

<td>

</td>

<td>

</td>

<td>

</td>

<td>RM(5,5) (32,32,1)

</td>

<td>

</td>

<td>

</td></tr>

<tr>

<td>

</td>

<td>

</td>

<td>

</td>

<td>

</td>

<td>RM(4,4) (16,16,1)

</td>

<td>

</td>

<td>RM(m − 1, m) (2m, 2m−1, 2)

</td>

<td><a href="Parity_bit" title="Parity bit">SPC</a> codes

</td></tr>

<tr>

<td>

</td>

<td>

</td>

<td>

</td>

<td>RM(3,3) (8,8,1)

</td>

<td>

</td>

<td>RM(4,5) (32,31,2)

</td></tr>

<tr>

<td>

</td>

<td>

</td>

<td>RM(2,2) (4,4,1)

</td>

<td>

</td>

<td>RM(3,4) (16,15,2)

</td>

<td>

</td>

<td>RM(m − 2, m) (2m, 2m−m−1, 4)

</td>

<td>extended <a href="Hamming_code" title="Hamming code">Hamming codes</a>

</td></tr>

<tr>

<td>

</td>

<td>RM(1,1) (2,2,1)

</td>

<td>

</td>

<td>RM(2,3) (8,7,2)

</td>

<td>

</td>

<td>RM(3,5) (32,26,4)

</td></tr>

<tr>

<td>RM(0,0) (1,1,1)

</td>

<td>

</td>

<td>RM(1,2) (4,3,2)

</td>

<td>

</td>

<td>RM(2,4) (16,11,4)

</td></tr>

<tr>

<td>

</td>

<td>RM(0,1) (2,1,2)

</td>

<td>

</td>

<td>RM(1,3) (8,4,4)

</td>

<td>

</td>

<td>RM(2,5) (32,16,8)

</td>

<td>RM(r, m=2r+1) (22r+1, 22r, 2r+1)

</td>

<td><a href="Self-dual_code" class="mw-redirect" title="Self-dual code">self-dual codes</a>

</td></tr>

<tr>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \infty }</annotation>

</semantics>

</math><img src="./c26c105004f30c27aa7c2a9c601550a4183b1f21.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.324ex; height:1.676ex;" alt="{\displaystyle \infty }" loading="lazy">)

</td>

<td>

</td>

<td>RM(0,2) (4,1,4)

</td>

<td>

</td>

<td>RM(1,4) (16,5,8)

</td></tr>

<tr>

<td>

</td>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \infty }</annotation>

</semantics>

</math><img src="./c26c105004f30c27aa7c2a9c601550a4183b1f21.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.324ex; height:1.676ex;" alt="{\displaystyle \infty }" loading="lazy">)

</td>

<td>

</td>

<td>RM(0,3) (8,1,8)

</td>

<td>

</td>

<td>RM(1,5) (32,6,16)

</td></tr>

<tr>

<td>

</td>

<td>

</td>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \infty }</annotation>

</semantics>

</math><img src="./c26c105004f30c27aa7c2a9c601550a4183b1f21.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.324ex; height:1.676ex;" alt="{\displaystyle \infty }" loading="lazy">)

</td>

<td>

</td>

<td>RM(0,4) (16,1,16)

</td>

<td>

</td>

<td>RM(1,m) (2m, m+1, 2m−1)

</td>

<td>punctured <a href="Hadamard_code" title="Hadamard code">Hadamard codes</a>

</td></tr>

<tr>

<td>

</td>

<td>

</td>

<td>

</td>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \infty }</annotation>

</semantics>

</math><img src="./c26c105004f30c27aa7c2a9c601550a4183b1f21.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.324ex; height:1.676ex;" alt="{\displaystyle \infty }" loading="lazy">)

</td>

<td>

</td>

<td>RM(0,5) (32,1,32)

</td></tr>

<tr>

<td>

</td>

<td>

</td>

<td>

</td>

<td>

</td>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \infty }</annotation>

</semantics>

</math><img src="./c26c105004f30c27aa7c2a9c601550a4183b1f21.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.324ex; height:1.676ex;" alt="{\displaystyle \infty }" loading="lazy">)

</td>

<td>

</td>

<td>RM(0,m) (2m, 1, 2m)

</td>

<td><a href="Repetition_code" title="Repetition code">repetition codes</a>

</td></tr>

<tr>

<td>

</td>

<td>

</td>

<td>

</td>

<td>

</td>

<td>

</td>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \infty }</annotation>

</semantics>

</math><img src="./c26c105004f30c27aa7c2a9c601550a4183b1f21.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.324ex; height:1.676ex;" alt="{\displaystyle \infty }" loading="lazy">)

</td></tr>

<tr>

<td>

</td>

<td>

</td>

<td>

</td>

<td>

</td>

<td>

</td>

<td>

</td>

<td>RM(−1,m) (2m, 0, ∞)

</td>

<td>trivial codes

</td></tr></tbody></table>

<div class="mw-heading mw-heading3"><h3 id="Properties_of_RM(r,m)_codes_for_r≤1_or_r≥m-1">Properties of RM(r,m) codes for r≤1 or r≥m-1</h3></div>

<ul><li>RM(0, m) codes are <a href="Repetition_code" title="Repetition code">repetition codes</a> of length N = 2m, <a href="Code_rate" title="Code rate">rate</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {R={\tfrac {1}{N}}}}">

<mfrac>

</mfrac>

</mstyle>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {R={\tfrac {1}{N}}}}</annotation>

</semantics>

</math><img src="./8ae126144850fd344ff5e3e37a18ec1609bebf03.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.171ex; width:7.158ex; height:3.509ex;" alt="{\displaystyle {R={\tfrac {1}{N}}}}" loading="lazy"> and minimum distance <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle d_{\min }=N}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle d_{\min }=N}</annotation>

</semantics>

</math><img src="./65bb69f7fdd3e9a6bc08359dd34fd75c01f4d573.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:9.343ex; height:2.509ex;" alt="{\displaystyle d_{\min }=N}" loading="lazy">.</li>

<li>RM(1, m) codes are <a href="Low-density_parity-check_code" title="Low-density parity-check code">parity check codes</a> of length N = 2m, rate <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle R={\tfrac {m+1}{N}}}">

<mfrac>

<mrow>

</mrow>

</mfrac>

</mstyle>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle R={\tfrac {m+1}{N}}}</annotation>

</semantics>

</math><img src="./fc810e6ecf78e6febaad4b3392ddce4530eb3943.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.171ex; width:9.242ex; height:3.676ex;" alt="{\displaystyle R={\tfrac {m+1}{N}}}" loading="lazy"> and minimum distance <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle d_{\min }={\tfrac {N}{2}}}">

<msub>

</mrow>

</msub>

<mfrac>

</mfrac>

</mstyle>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle d_{\min }={\tfrac {N}{2}}}</annotation>

</semantics>

</math><img src="./e90b14be9ca04f5fd5974f361dbc6b1b7b5d5ba2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.171ex; width:9.575ex; height:3.509ex;" alt="{\displaystyle d_{\min }={\tfrac {N}{2}}}" loading="lazy">.</li>

<li>RM(m − 1, m) codes are <a href="Low-density_parity-check_code" title="Low-density parity-check code">single parity check codes</a> of length N = 2m, rate <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle R={\tfrac {N-1}{N}}}">

<mfrac>

<mrow>

</mrow>

</mfrac>

</mstyle>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle R={\tfrac {N-1}{N}}}</annotation>

</semantics>

</math><img src="./b1f6c497aab9b5c7e0c32f07b03989a2b8a90c07.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.171ex; width:9.258ex; height:3.676ex;" alt="{\displaystyle R={\tfrac {N-1}{N}}}" loading="lazy"> and minimum distance <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle d_{\min }=2}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle d_{\min }=2}</annotation>

</semantics>

</math><img src="./9d119323c9c158dba93c4b3ab1c9740d6adbfc74.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:8.442ex; height:2.509ex;" alt="{\displaystyle d_{\min }=2}" loading="lazy">.</li>

<li>RM(m − 2, m) codes are the family of <a href="Hamming_code" title="Hamming code">extended Hamming codes</a> of length N = 2m with minimum distance <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle d_{\min }=4}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle d_{\min }=4}</annotation>

</semantics>

</math><img src="./c3075708f03c5d64f7af12f86422754652e2dbbf.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:8.442ex; height:2.509ex;" alt="{\displaystyle d_{\min }=4}" loading="lazy">.<a href="#cite_note-7">[7]</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFMassey1992" class="citation cs2">Massey, James L. (1992), "Deep-space communications and coding: A marriage made in heaven", Advanced Methods for Satellite and Deep Space Communications, Lecture Notes in Control and Information Sciences, vol. 182, Springer-Verlag, pp. 1–17, <a href="CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.36.4265">10.1.1.36.4265</a>, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2Fbfb0036046">10.1007/bfb0036046</a>, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-3540558514</bdi></cite><a rel="nofollow" class="external text" href="https://www.isiweb.ee.ethz.ch/archive/massey_pub/pdf/BI321.pdf">pdf</a>

</li>

<li id="cite_note-2"><a href="#cite_ref-2">^</a> <cite class="citation web cs1"><a rel="nofollow" class="external text" href="http://www.3gpp.org/ftp/tsg_ran/WG1_RL1/TSGR1_87/Report/Final_Minutes_report_RAN1%2387_v100.zip">"3GPP RAN1 meeting #87 final report"</a>. 3GPP. Retrieved 31 August 2017.</cite>

</li>

<li id="cite_note-3"><a href="#cite_ref-3">^</a> <cite id="CITEREFArikan2009" class="citation journal cs1">Arikan, Erdal (2009). "Channel Polarization: A Method for Constructing Capacity-Achieving Codes for Symmetric Binary-Input Memoryless Channels - IEEE Journals & Magazine". IEEE Transactions on Information Theory. 55 (7): 3051–3073. <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/0807.3917">0807.3917</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2FTIT.2009.2021379">10.1109/TIT.2009.2021379</a>. <a href="Hdl_(identifier)" class="mw-redirect" title="Hdl (identifier)">hdl</a>:<a rel="nofollow" class="external text" href="https://hdl.handle.net/11693%2F11695">11693/11695</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:889822">889822</a>.</cite>

</li>

<li id="cite_note-4"><a href="#cite_ref-4">^</a> <cite id="CITEREFMuller1954" class="citation journal cs1">Muller, David E. (1954). "Application of Boolean algebra to switching circuit design and to error detection". Transactions of the I.R.E. Professional Group on Electronic Computers. EC-3 (3): 6–12. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2Firepgelc.1954.6499441">10.1109/irepgelc.1954.6499441</a>. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/2168-1740">2168-1740</a>.</cite>

</li>

<li id="cite_note-5"><a href="#cite_ref-5">^</a> <cite id="CITEREFReed1954" class="citation journal cs1">Reed, Irving S. (1954). "A class of multiple-error-correcting codes and the decoding scheme". Transactions of the IRE Professional Group on Information Theory. 4 (4): 38–49. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2Ftit.1954.1057465">10.1109/tit.1954.1057465</a>. <a href="Hdl_(identifier)" class="mw-redirect" title="Hdl (identifier)">hdl</a>:<a rel="nofollow" class="external text" href="https://hdl.handle.net/10338.dmlcz%2F143797">10338.dmlcz/143797</a>. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/2168-2690">2168-2690</a>.</cite>

</li>

<li id="cite_note-6"><a href="#cite_ref-6">^</a> Prahladh Harsha et al., <a href="https://arxiv.org/abs/1002.3864" class="extiw external" title="arxiv:1002.3864">Limits of Approximation Algorithms: PCPs and Unique Games (DIMACS Tutorial Lecture Notes)</a>, Section 5.2.1.

</li>

<li id="cite_note-7"><a href="#cite_ref-7">^</a> Trellis and Turbo Coding, C. Schlegel & L. Perez, Wiley Interscience, 2004, p149.

</li>

</ol></div></div>

<div class="mw-heading mw-heading2"><h2 id="Further_reading">Further reading</h2></div>

<ul><li><cite id="CITEREFShu_LinDaniel_Costello2005" class="citation book cs1">Shu Lin; Daniel Costello (2005). Error Control Coding (2 ed.). Pearson. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-13-017973-9</bdi>.</cite> Chapter 4.</li>

<li><cite id="CITEREFJ.H._van_Lint1992" class="citation book cs1">J.H. van Lint (1992). <a rel="nofollow" class="external text" href="https://archive.org/details/introductiontoco0000lint">Introduction to Coding Theory</a>. <a href="Graduate_Texts_in_Mathematics" title="Graduate Texts in Mathematics">GTM</a>. Vol. 86 (2 ed.). <a href="Springer-Verlag" class="mw-redirect" title="Springer-Verlag">Springer-Verlag</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-3-540-54894-2</bdi>.</cite> Chapter 4.5.</li></ul>

<div class="mw-heading mw-heading2"><h2 id="External_links">External links</h2></div>

<ul><li><a rel="nofollow" class="external text" href="http://ocw.mit.edu">MIT OpenCourseWare</a>, 6.451 Principles of Digital Communication II, Lecture Notes section 6.4</li>

<li><a rel="nofollow" class="external text" href="http://octave.sourceforge.net/communications/function/reedmullergen.html">GPL Matlab-implementation of RM-codes </a></li>

<li><a rel="nofollow" class="external text" href="http://octave.svn.sourceforge.net/viewvc/octave/trunk/octave-forge/main/comm/inst/reedmullergen.m?revision=9852&view=markup">Source GPL Matlab-implementation of RM-codes</a></li>

<li><cite id="CITEREFWeiss1962" class="citation journal cs1">Weiss, E. (September 1962). "Generalized Reed-Muller codes". Information and Control. 5 (3): 213–222. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2Fs0019-9958%2862%2990555-7">10.1016/s0019-9958(62)90555-7</a>. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/0019-9958">0019-9958</a>.</cite></li></ul>

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbox{box-sizing:border-box;border:1px solid #a2a9b1;width:100%;clear:both;font-size:88%;text-align:center;padding:1px;margin:1em auto 0}.mw-parser-output .navbox .navbox{margin-top:0}.mw-parser-output .navbox+.navbox,.mw-parser-output .navbox+.navbox-styles+.navbox{margin-top:-1px}.mw-parser-output .navbox-inner,.mw-parser-output .navbox-subgroup{width:100%}.mw-parser-output .navbox-group,.mw-parser-output .navbox-title,.mw-parser-output .navbox-abovebelow{padding:0.25em 1em;line-height:1.5em;text-align:center}.mw-parser-output .navbox-group{white-space:nowrap;text-align:right}.mw-parser-output .navbox,.mw-parser-output .navbox-subgroup{background-color:#fdfdfd}.mw-parser-output .navbox-list{line-height:1.5em;border-color:#fdfdfd}.mw-parser-output .navbox-list-with-group{text-align:left;border-left-width:2px;border-left-style:solid}.mw-parser-output tr+tr>.navbox-abovebelow,.mw-parser-output tr+tr>.navbox-group,.mw-parser-output tr+tr>.navbox-image,.mw-parser-output tr+tr>.navbox-list{border-top:2px solid #fdfdfd}.mw-parser-output .navbox-title{background-color:#ccf}.mw-parser-output .navbox-abovebelow,.mw-parser-output .navbox-group,.mw-parser-output .navbox-subgroup .navbox-title{background-color:#ddf}.mw-parser-output .navbox-subgroup .navbox-group,.mw-parser-output .navbox-subgroup .navbox-abovebelow{background-color:#e6e6ff}.mw-parser-output .navbox-even{background-color:#f7f7f7}.mw-parser-output .navbox-odd{background-color:transparent}.mw-parser-output .navbox .hlist td dl,.mw-parser-output .navbox .hlist td ol,.mw-parser-output .navbox .hlist td ul,.mw-parser-output .navbox td.hlist dl,.mw-parser-output .navbox td.hlist ol,.mw-parser-output .navbox td.hlist ul{padding:0.125em 0}.mw-parser-output .navbox .navbar{display:block;font-size:100%}.mw-parser-output .navbox-title .navbar{float:left;text-align:left;margin-right:0.5em}body.skin--responsive .mw-parser-output .navbox-image img{max-width:none!important}@media print{body.ns-0 .mw-parser-output .navbox{display:none!important}}

/* end https://en.wikipedia.org/ */

</style></div><div role="navigation" class="navbox" aria-labelledby="Consultative_Committee_for_Space_Data_Systems222" style="padding:3px"><table class="nowraplinks mw-collapsible autocollapse navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><div id="Consultative_Committee_for_Space_Data_Systems222" style="font-size:114%;margin:0 4em"><a href="Consultative_Committee_for_Space_Data_Systems" title="Consultative Committee for Space Data Systems">Consultative Committee for Space Data Systems</a></div></th></tr><tr><th scope="row" class="navbox-group" style="width:1%">Data compression</th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li>Images

<li>Data

<ul><li><a href="Adaptive_coding" title="Adaptive coding">Adaptive Entropy Coder</a></li></ul></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Error Correction</th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<dl><dt>Current</dt>

<dd><a href="Binary_Golay_code" title="Binary Golay code">Binary Golay code</a></dd>

<dd><a href="Concatenated_error_correction_code" title="Concatenated error correction code">Concatenated codes</a></dd>

<dd><a href="Turbo_code" title="Turbo code">Turbo codes</a></dd>

<dt>Proposed</dt>

<dd><a href="Low-density_parity-check_code" title="Low-density parity-check code">LDPC codes</a></dd></dl>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Telemetry command uplink</th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Command-loss_timer" title="Command-loss timer">Command-loss timer</a></li>

<li><a href="Proximity-1_Space_Link_Protocol" title="Proximity-1 Space Link Protocol">Proximity-1 Space Link Protocol</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Telemetry downlink</th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Spacecraft_Monitoring_%26_Control" class="mw-redirect" title="Spacecraft Monitoring & Control">Spacecraft Monitoring & Control</a></li>

<li><a href="Beacon_mode_service" title="Beacon mode service">Beacon mode service</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Telemetry general</th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Space_Communications_Protocol_Specifications" title="Space Communications Protocol Specifications">Space Communications Protocol Specifications</a> (SCPS): <a href="Performance_Enhancing_Proxy" class="mw-redirect" title="Performance Enhancing Proxy">Performance Enhancing Proxy</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Telemetry modulation systems</th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<dl><dt>Current</dt>

<dd><a href="OQPSK" class="mw-redirect" title="OQPSK">OQPSK</a></dd>

<dt>Proposed</dt>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Frequencies</th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Networking, interoperability and monitoring</th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Service-oriented_architecture" title="Service-oriented architecture">Service-oriented architecture</a> (<a href="Message_Abstraction_Layer" title="Message Abstraction Layer">Message Abstraction Layer</a>)</li></ul>

</div></td></tr></tbody></table></div></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-02-05" href="https://en.wikipedia.org/wiki/?title=Reed%E2%80%93Muller_code&oldid=1274193114">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>